package argo.hot100;

/**
 * 接雨水问题
 */
public class Trap {

    public int trap(int[] height) {
        int res = 0;

        int left = 0, leftHeightMax = 0, right = height.length - 1, rightHeightMax = 0;

        while (left < right) {

            if (height[left] < height[right]) {
                leftHeightMax = Math.max(height[left], leftHeightMax);
                res = res + leftHeightMax - height[left];
                left++;
            } else {
                rightHeightMax = Math.max(height[right], rightHeightMax);
                res = res + rightHeightMax - height[right];
                right--;
            }

        }

        return res;
    }

    public static void main(String[] args) {
        System.out.println(new Trap().trap(new int[]{0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1}));
        System.out.println(new Trap().trap(new int[]{4,2,3}));
    }
}
